home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1994 March / Internet Info CD-ROM (Walnut Creek) (March 1994).iso / answers / comp / ai-faq / genetic / part3 < prev    next >
Text File  |  1994-03-18  |  40KB  |  763 lines
  1. Newsgroups: comp.ai.genetic,comp.answers,news.answers
  2. Path: bloom-beacon.mit.edu!hookup!swrinde!cs.utexas.edu!howland.reston.ans.net!EU.net!uknet!cf-cm!cf.cm.ac.uk!David.Beasley
  3. From: David.Beasley@cf.cm.ac.uk (David Beasley)
  4. Subject: FAQ: comp.ai.genetic part 3/6 (A Guide to Frequently Asked Questions)
  5. Message-ID: <part3_764003894@cm.cf.ac.uk>
  6. Followup-To: comp.ai.genetic
  7. Summary: This is part 3 of a <trilogy> entitled "The Hitch-Hiker's Guide to 
  8.          Evolutionary Computation". A periodically published list of 
  9.          Frequently Asked Questions (and their answers) about Evolutionary 
  10.          Algorithms, Life and Everything. It should be read by anyone who 
  11.          whishes to post to the comp.ai.genetic newsgroup, preferably *before* 
  12.          posting.
  13. Originator: David.Beasley@cf.cm.ac.uk (David Beasley)
  14. Sender: David.Beasley@cf.cm.ac.uk (David Beasley)
  15. Supersedes: <part3_757015572@cm.cf.ac.uk>
  16. Organization: University of Wales College of Cardiff, Cardiff, WALES, UK.
  17. References: <part2_764003894@cm.cf.ac.uk>
  18. Date: Fri, 18 Mar 94 15:19:16 GMT
  19. Approved: news-answers-request@MIT.Edu
  20. Expires: 30 Jun 1994 15:18:14 GMT
  21. Lines: 739
  22. Xref: bloom-beacon.mit.edu comp.ai.genetic:2506 comp.answers:4206 news.answers:16512
  23.  
  24. Archive-name:   ai-faq/genetic/part3
  25. Last-Modified:  3/20/94
  26. Issue:          2.1
  27.  
  28. TABLE OF CONTENTS OF PART 3
  29.      Q2: What applications of EAs are there?
  30.  
  31.      Q3: Who is concerned with EAs?
  32.  
  33.      Q4: How many EAs exist? Which?
  34.      Q4.1: What about Alife systems, like Tierra and VENUS?
  35.  
  36.      Q5: What about all this Optimization stuff?
  37.  
  38. ----------------------------------------------------------------------
  39.  
  40. Subject: Q2: What applications of EAs are there?
  41.  
  42.      In   principle,   EAs  can  compute  any  computable  function,  i.e.
  43.      everything a normal digital computer can do.
  44.  
  45.      But EAs are especially badly suited for problems where efficient ways
  46.      of  solving  them  are  already  known,  (unless  these  problems are
  47.      intended to serve as benchmarks).  Special purpose  algorithms,  i.e.
  48.      algorithms  that  have  a  certain amount of problem domain knowledge
  49.      hard coded into them, will usually outperform EAs,  so  there  is  no
  50.      black  magic  in EC.  EAs should be used when there is no other known
  51.      problem solving strategy, and  the  problem  domain  is  NP-complete.
  52.      That's  where  EAs  come  into  play: heuristically finding solutions
  53.      where all else fails.
  54.  
  55.      Following  is  an  incomplete   (sic!)    list   of   successful   EA
  56.      applications:
  57.  
  58.  TIMETABLING
  59.      This  has  been addressed quite successfully with GAs.  A very common
  60.      manifestation of this kind of problem is the timetabling of exams  or
  61.      classes  in  Universities,  etc.  At  the  Department  of  Artificial
  62.      Intelligence, University of Edinburgh, timetabling the MSc  exams  is
  63.      now done using a GA (Corne et al. 93, Fang 92). An example of the use
  64.      of GAs for timetabling classes is (Abramson & Abela 1991).
  65.  
  66.      In the exam timetabling case,  the  FITNESS  function  for  a  GENOME
  67.      representing a timetable involves computing degrees of punishment for
  68.      various problems with the timetable, such as  clashes,  instances  of
  69.      students  having  to  take  consecutive  exams, instances of students
  70.      having (eg) three or more exams in  one  day,  the  degree  to  which
  71.      heavily-subscribed  exams  occur  late  in the timetable (which makes
  72.      marking harder), overall length of timetable, etc. The modular nature
  73.      of the fitness function has the key to the main potential strength of
  74.      using GAs for this sort of thing as  opposed  to  using  conventional
  75.      search  and/or  constraint  programming  methods. The power of the GA
  76.      approach is the ease with which it  can  handle  arbitrary  kinds  of
  77.      constraints  and  objectives;  all  such  things  can  be  handled as
  78.      weighted components of the fitness function, making it easy to  adapt
  79.      the  GA  to  the  particular  requirements  of  a  very wide range of
  80.      possible overall objectives . Very few other timetabling methods, for
  81.      example,  deal with such objectives at all, which shows how difficult
  82.      it is (without  GAs)  to  graft  the  capacity  to  handle  arbitrary
  83.      objectives  onto  the  basic "find shortest- length timetable with no
  84.      clashes" requirement.  The  proper  way  to  weight/handle  different
  85.      objectives  in  the  fitness  function  in relation to the general GA
  86.      dynamics remains, however, an important research problem!
  87.      GAs thus offer a combination of simplicity, flexibility & speed which
  88.      competes  very  favorably  with other approaches, but are unlikely to
  89.      outperform  knowledge-based  (etc)  methods  if  the  best   possible
  90.      solution  is  required at any cost. Even then, however, hybridisation
  91.      may yield the best of both worlds; also, the ease (if the hardware is
  92.      available!)  of implementing GAs in parallel enhances the possibility
  93.      of using them for good, fast solutions to very hard  timetabling  and
  94.      similar problems.
  95.  
  96.      References
  97.  
  98.      Corne,  D. Fang, H.-L. & Mellish, C. (1993) "Solving the Modular Exam
  99.      Scheduling Problem with Genetic  Algorithms".   Proc.  of  6th  Int'l
  100.      Conf.  on  Industrial  and  Engineering  Applications  of  Artificial
  101.      Intelligence & Expert Systems, ISAI, (to appear).
  102.  
  103.      Fang,  H.-L.  (1992)  "Investigating   GAs   for   scheduling",   MSc
  104.      Dissertation,   University   of   Edinburgh   Dept.   of   Artificial
  105.      Intelligence, Edinburgh, UK.
  106.  
  107.      Abramson & Abela (1991) "A Parallel Genetic Algorithm for Solving the
  108.      School  Timetabling  Problem",  Technical  Report,  Division of I.T.,
  109.      C.S.I.R.O,  April  1991.   (Division   of   Information   Technology,
  110.      C.S.I.R.O.,  c/o  Dept.  of  Communication  & Electronic Engineering,
  111.      Royal Melbourne Institute of  Technology,  PO  BOX  2476V,  Melbourne
  112.      3001, Australia)
  113.  
  114.  JOB-SHOP SCHEDULING
  115.      The  Job-Shop  Scheduling  Problem  (JSSP)  is  a  very difficult NP-
  116.      complete problem which, so far, seems best addressed by sophisticated
  117.      branch  and  bound  search  techniques.  GA researchers, however, are
  118.      continuing to make  progress  on  it.   (Davis  85)  started  off  GA
  119.      research  on  the  JSSP,  (Whitley  89)  reports  on  using  the edge
  120.      RECOMBINATION operator (designed initially for the TSP) on JSSPs too.
  121.      More  recent work includes (Nakano 91),(Yamada & Nakano 92), (Fang et
  122.      al. 93).  The latter three  report  increasingly  better  results  on
  123.      using  GAs on fairly large benchmark JSSPs (from Muth & Thompson 63);
  124.      neither consistently outperform branch & bound search yet,  but  seem
  125.      well  on  the  way.  A  crucial  aspect  of such work (as with any GA
  126.      application) is the method used to  encode  schedules.  An  important
  127.      aspect of some of the recent work on this is that better results have
  128.      been obtained by rejecting the conventional wisdom  of  using  binary
  129.      representations   (as  in  (Nakano  91))  in  favor  of  more  direct
  130.      encodings. In (Yamada & Nakano 92), for example,  a  GENOME  directly
  131.      encodes operation completion times, while in (Fang et al. 93) genomes
  132.      represent implicit instructions for building a schedule. The  success
  133.      of  these  latter techniques, especially since their applications are
  134.      very important in industry, should eventually spawn  advances  in  GA
  135.      theory.
  136.  
  137.      Concerning  the point of using GAs at all on hard job-shop scheduling
  138.      problems, the same goes here as suggested  above  for  `Timetabling':
  139.      The   GA   approach  enables  relatively  arbitrary  constraints  and
  140.      objectives to be incorporated painlessly into a  single  OPTIMIZATION
  141.      method.   It   is  unlikely  that  GAs  will  outperform  specialized
  142.      knowledge-based  and/or  conventional  OR-based  approaches  to  such
  143.      problems  in  terms  of  raw solution quality, however GAs offer much
  144.      greater simplicity and flexibility, and so, for example, may  be  the
  145.      best method for quick high-quality solutions, rather than finding the
  146.      best possible solution at any cost. Also, of course,  hybrid  methods
  147.      will  have a lot to offer, and GAs are far easier to parallelize than
  148.      typical knowledge-based/OR methods.
  149.  
  150.      Similar to the JSSP is  the  Open  Shop  Scheduling  Problem  (OSSP).
  151.      (Fang  et  al.  93) reports an initial attempt at using GAs for this.
  152.      Ongoing results from the same source shows  reliable  achievement  of
  153.      results  within  less than 0.23% of optimal on moderately large OSSPs
  154.      (so far, up to 20x20), including an  improvement  on  the  previously
  155.      best known solution for a benchmark 10x10 OSSP. A simpler form of job
  156.      shop problem is the Flow-Shop Sequencing problem;  recent  successful
  157.      work on applying GAs to this includes (Reeves 93)."
  158.  
  159.      References
  160.      Davis,  L.  (1985)  "Job-Shop  Scheduling  with  Genetic Algorithms",
  161.      [ICGA85], 136-140.
  162.  
  163.      Muth, J.F. & Thompson, G.L. (1963) "Industrial Scheduling".  Prentice
  164.      Hall, Englewood Cliffs, NJ, 1963.
  165.  
  166.      Nakano,  R.  (1991)  "Conventional  Genetic  Algorithms  for Job-Shop
  167.      Problems", [ICGA91], 474-479.
  168.  
  169.      Reeves, C.R. (1993) "A Genetic Algorithm  for  Flowshop  Sequencing",
  170.      Coventry Polytechnic Working Paper, Coventry, UK.
  171.  
  172.      Whitley,  D.,  Starkweather,  T.  &  D'Ann  Fuquay (1989) "Scheduling
  173.      Problems and  Traveling  Salesmen:  The  Genetic  Edge  Recombination
  174.      Operator", [ICGA89], 133-140.
  175.  
  176.      Fang,  H.-L.,  Ross,  P.,  &  Corne  D.  (1993)  "A Promising Genetic
  177.      Algorithm Approach to Job-Shop Scheduling, Rescheduling  &  Open-Shop
  178.      Scheduling Problems", [ICGA93], 375-382.
  179.  
  180.      Yamada,  T.  &  Nakano,  R. (1992) "A Genetic Algorithm Applicable to
  181.      Large-Scale Job-Shop Problems", [PPSN92], 281-290.
  182.  
  183.  MANAGEMENT SCIENCES
  184.      "Applications of EA in management science and closely related  fields
  185.      like organizational ecology is a domain that has been covered by some
  186.      EA researchers - with considerable bias towards scheduling  problems.
  187.      Since  I believe that EA have considerable potential for applications
  188.      outside  the  rather  narrow  domain  of   scheduling   and   related
  189.      combinatorial  problems,  I  started  collecting references about the
  190.      status quo of EA-applications in  management  science.   This  report
  191.      intends  to  make  available  my findings to other researchers in the
  192.      field. It is a short  overview  and  lists  some  230  references  to
  193.      current as well as finished research projects.  [..]
  194.  
  195.      "At  the end of the paper, a questionnaire has been incorporated that
  196.      may be used for this purpose. Other comments are also appreciated."
  197.  
  198.      --- from the Introduction of (Nissen 93)
  199.  
  200.      References
  201.  
  202.      Nissen, V. (1993) "Evolutionary Algorithms in Management Science:  An
  203.      Overview  and List of References", Papers on Economics and Evolution,
  204.      edited by the European Study Group for Evolutionary Economics.   This
  205.      report     is     also     avail.     via     anon.      FTP     from
  206.      gwdu03.gwdg.de:/pub/msdos/reports/wi/earef.eps
  207.  
  208.      Boulding, K.E. (1991) "What is evolutionary economics?",  Journal  of
  209.      Evolutionary Economics, 1, 9-17.
  210.  
  211.  GAME PLAYING
  212.      GAs  can  be  used  to  evolve  behaviors  for playing games. Work in
  213.      evolutionary GAME THEORY  typically  surrounds  the  EVOLUTION  of  a
  214.      POPULATION  of players who meet randomly to play a game in which they
  215.      each must adopt one of a  limited  number  of  moves.  (Maynard-Smith
  216.      1982).   Let's  suppose  it  is  just two moves, X and Y. The players
  217.      receive a reward, analogous to Darwinian FITNESS, depending on  which
  218.      combination  of  moves  occurs  and  which move they adopted. In more
  219.      complicated models there may be several players and several moves.
  220.  
  221.      The players iterate such a game a series of times, and then  move  on
  222.      to a new partner. At the end of all such moves, the players will have
  223.      a cumulative payoff, their FITNESS.  This fitness can then be used as
  224.      a  means  of conducting something akin to Roulette-Wheel SELECTION to
  225.      generate a new POPULATION.
  226.      The real key in using a  GA  is  to  come  up  with  an  encoding  to
  227.      represent  player's strategies, one that is amenable to CROSSOVER and
  228.      to MUTATION.  possibilities are to suppose at each iteration a player
  229.      adopts  X with some probability (and Y with one minus such). A player
  230.      can thus be  represented  as  a  real  number,  or  a  bit-string  by
  231.      interpreting  the  decimal  value of the bit string as the inverse of
  232.      the probability.
  233.  
  234.      An alternative characterisation is to model  the  players  as  Finite
  235.      State  Machines, or Finite Automata (FA). These can be though of as a
  236.      simple flow chart governing behaviour in the "next" play of the  game
  237.      depending upon previous plays. For example:
  238.  
  239.       100 Play X
  240.       110 If opponent plays X go to 100
  241.       120 Play Y
  242.       130 If opponent plays X go to 100 else go to 120
  243.      Represents  a  strategy that does whatever its opponent did last, and
  244.      begins by playing X, known as  "Tit-For-Tat."  (Axelrod  1982).  Such
  245.      machines can readily be encoded as bit-strings. Consider the encoding
  246.      "1 0 1 0 0 1" to represent TFT.  The first three bits, "1  0  1"  are
  247.      state  0.  The  first bit, "1" is interpreted as "Play X." The second
  248.      bit, "0" is interpreted as "if opponent plays X go to state  1,"  the
  249.      third  bit,  "1",  is  interpreted as "if the opponent plays Y, go to
  250.      state 1."  State 1 has a similar interpretation. Crossing  over  such
  251.      bit-strings always yields valid strategies.
  252.  
  253.      SIMULATIONs  in  the Prisoner's dilemma have been undertaken (Axelrod
  254.      1987, Fogel 1993, Miller 1989) of these machines.
  255.  
  256.      Alternative  representations  of  game  players  include   CLASSIFIER
  257.      SYSTEMs  (Marimon, McGrattan and Sargent 1990, [GOLD89]), and Neural-
  258.      networks (Fogel and Harrald 1994), though not necessarily with a  GA.
  259.      (Fogel  1993),  and  Fogel  and  Harrald  1994  use  an  Evolutionary
  260.      Program).
  261.  
  262.      Other methods of evolving a POPULATION can be found in Lindgren 1991,
  263.      Glance and Huberman 1993 and elsewhere.
  264.  
  265.      References.
  266.  
  267.      Axelrod,  R.  (1987)  ``The  EVOLUTION  of Strategies in the Repeated
  268.      Prisoner's Dilemma,'' in [DAVIS91]
  269.  
  270.      Miller, J.H. (1989) ``The Coevolution of  Automata  in  the  Repeated
  271.      Prisoner's Dilemma'' Santa Fe Institute Working Paper 89-003.
  272.  
  273.      Marimon,  Ramon, Ellen McGrattan and Thomas J. Sargent (1990) ``Money
  274.      as a Medium of Exchange in an Economy with  Artificially  Intelligent
  275.      Agents'' Journal of Economic Dynamics and Control 14, pp. 329--373.
  276.  
  277.      Maynard-Smith, (1982) EVOLUTION and the Theory of Games, CUP.
  278.  
  279.      Lindgren  (1991)  ``Evolutionary  Phenomena  in Simple Dynamics,'' in
  280.      [ALIFEI].
  281.  
  282.      Holland, J.H and John Miller (1990) ``Artificially Adaptive Agents in
  283.      Economic  Theory,''  American Economic Review: Papers and Proceedings
  284.      of the 103rd Annual Meeting of the  American  Economics  Association:
  285.      365--370.
  286.  
  287.      Huberman,  Bernado,  and  Natalie  S.  Glance  (1993)  "Diversity and
  288.      Collective  Action"   in   H.   Haken   and   A.   Mikhailov   (eds.)
  289.      Interdisciplinary Approaches to Nonlinear Systems, Springer.
  290.  
  291.      Fogel  (1993)  "Evolving Behavior in the Iterated Prisoner's Dilemma"
  292.      EVOLUTIONARY COMPUTATION 1:1
  293.  
  294.      Fogel, D.B. and Paul Harrald (1994) ``Evolving Complex  Behaviour  in
  295.      the  Iterated  Prisoner's Dilemma,'' Proceedings of the Fourth Annual
  296.      Meetings of the EVOLUTIONARY PROGRAMMING Society, L.J. Fogel and A.W.
  297.      Sebald eds., World Science Press.
  298.  
  299. ------------------------------
  300.  
  301. Subject: Q3: Who is concerned with EAs?
  302.  
  303.      EVOLUTIONARY  COMPUTATION  attracts  researchers  and people of quite
  304.      dissimilar disciplines, i.e.   EC  is  a  interdisciplinary  research
  305.      field:
  306.  
  307.  Computer scientists
  308.      Want  to  find  out  about the properties of sub-symbolic information
  309.      processing with EAs and about learning,  i.e.   adaptive  systems  in
  310.      general.
  311.  
  312.      They   also  build  the  hardware  necessary  to  enable  future  EAs
  313.      (precursors are already beginning  to  emerge)  to  huge  real  world
  314.      problems,  i.e. the term "massively parallel computation" [HILLIS92],
  315.      springs to mind.
  316.  
  317.  Engineers
  318.      Of many kinds want to exploit the capabilities of EAs on  many  areas
  319.      to solve their application, esp.  OPTIMIZATION problems.
  320.  
  321.  Roboticists
  322.      Want  to  build  MOBOTs (MOBile ROBOTs, i.e. R2D2's and #5's cousins)
  323.      that navigate through uncertain ENVIRONMENTs, without using  built-in
  324.      "maps".   The  MOBOTS  thus  have to adapt to their surroundings, and
  325.      learn what they can do "move-through-door" and what they can't "move-
  326.      through-wall" on their own by "trial-and-error".
  327.  
  328.  Cognitive scientists
  329.      Might view CFS as a possible apparatus to describe models of thinking
  330.      and cognitive systems.
  331.  
  332.  Physicists
  333.      Use EC hardware, e.g. Hillis' (Thinking Machine  Corp.'s)  Connection
  334.      Machine  to  model  real  world  problems  which include thousands of
  335.      variables, that run "naturally" in parallel, and thus can be modelled
  336.      more  easily  and  esp.   "faster"  on  a parallel machine, than on a
  337.      serial "PC" one.
  338.  
  339.  Biologists
  340.      In fact many working biologists  are  hostile  to  modeling,  but  an
  341.      entire   community   of   Population   Biologists   arose   with  the
  342.      'evolutionary synthesis' of the 1930's created by the polymaths  R.A.
  343.      Fisher,  J.B.S.  Haldane, and S. Wright.  Wright's SELECTION in small
  344.      POPULATIONs, thereby avoiding local optima) is of current interest to
  345.      both biologists and ECers -- populations are naturally parallel.
  346.  
  347.      A  good  exposition  of  current  POPULATION  Biology  modeling is J.
  348.      Maynard Smith's text Evolutionary Genetics.  Richard Dawkin's Selfish
  349.      Gene and Extended Phenotype are unparalleled (sic!) prose expositions
  350.      of  evolutionary  processes.   Rob  Collins'  papers  are   excellent
  351.      parallel  GA  models of evolutionary processes (available in [ICGA91]
  352.      and by FTP from ftp.cognet.ucla.edu:/pub/alife/papers/ ).
  353.  
  354.      As fundamental motivation, consider Fisher's comment:  "No  practical
  355.      biologist  interested  in  (e.g.) sexual REPRODUCTION would be led to
  356.      work out the detailed consequences experienced  by  organisms  having
  357.      three  or more sexes; yet what else should [s/]he do if [s/]he wishes
  358.      to understand why the sexes are, in fact, always two?"  (Three  sexes
  359.      would make for even weirder grammar, [s/]he said...)
  360.  
  361.  Philosophers
  362.      and some other really curious people may also be interested in EC for
  363.      various reasons.
  364.  
  365.  
  366. ------------------------------
  367.  
  368. Subject: Q4: How many EAs exist? Which?
  369.  
  370.  The All Stars
  371.      There  are  currently  3  main  paradigms  in  EA  research:  GENETIC
  372.      ALGORITHMs,   EVOLUTIONARY  PROGRAMMING,  and  EVOLUTION  STRATEGIEs.
  373.      CLASSIFIER SYSTEMs and GENETIC PROGRAMMING are OFFSPRING  of  the  GA
  374.      community.   Besides  this  leading  crop,  there  are numerous other
  375.      different approaches, alongside hybrid experiments, i.e. there  exist
  376.      pieces  of software residing in some researchers computers, that have
  377.      been described in papers in conference proceedings, and  may  someday
  378.      prove  useful  on certain tasks. To stay in EA slang, we should think
  379.      of these evolving strands as BUILDING BLOCKs,  that  when  recombined
  380.      someday,  will  produce  new  offspring  and  give  birth  to  new EA
  381.      paradigm(s).
  382.  
  383.  Promising Rookies
  384.      As far as "solving complex function  and  COMBINATORIAL  OPTIMIZATION
  385.      tasks"  is  concerned, Davis' work on real-valued representations and
  386.      adaptive operators should be mentioned (Davis 89). Moreover Whitley's
  387.      Genitor  system  incorporating  ranking  and "steady state" mechanism
  388.      (Whitley   89),   Goldberg's   "messy   GAs",    involves    adaptive
  389.      representations (Goldberg 91), and Eshelman's CHC algorithm (Eshelman
  390.      91).
  391.  
  392.      For  "the  design  of  robust  learning  systems",  i.e.  the   field
  393.      characterized  by  CFS, Holland's (1986) CLASSIFIER SYSTEM, with it's
  394.      state-of-the-art implementation CFS-C  (Riolo  88),  we  should  note
  395.      recent  developments  in  SAMUEL  (Grefenstette 89), GABIL (De Jong &
  396.      Spears 91), and GIL (Janikow 91).
  397.  
  398.      References
  399.  
  400.      Davis,  L.  (1989)  "Adapting  operator  probabilities   in   genetic
  401.      algorithms", [ICGA89], 60-69.
  402.  
  403.      Whitley,  D.  et  al.  (1989)  "The  GENITOR  algorithm and SELECTION
  404.      pressure: why rank-based allocation of reproductive trials is  best",
  405.      [ICGA89], 116-121.
  406.  
  407.      Goldberg,  D. et al. (1991) "Don't worry, be messy", [ICGA91], 24-30.
  408.  
  409.      Eshelman, L.J. et al. (1991)  "Preventing  premature  convergence  in
  410.      GENETIC ALGORITHMs by preventing incest", [ICGA91], 115-122.
  411.  
  412.      Holland,  J.H.  (1986)  "Escaping  brittleness:  The possibilities of
  413.      general-purpose learning algorithms applied  to  parallel  rule-based
  414.      systems".   In R. Michalski, J. Carbonell, T. Mitchell (eds), Machine
  415.      Learning: An ARTIFICIAL  INTELLIGENCE  Approach.  Los  Altos:  Morgan
  416.      Kaufmann.
  417.      Riolo,   R.L.   (1988)   "CFS-C:  A  package  of  domain  independent
  418.      subroutines for implementing CLASSIFIER SYSTEMs in  arbitrary,  user-
  419.      defined   environments".   Logic  of  computers  group,  Division  of
  420.      computer science and engineering, University of Michigan.
  421.  
  422.      Grefenstette, J.J. (1989) "A system for learning  control  strategies
  423.      with genetic algorithms", [ICGA89], 183-190.
  424.      De  Jong  K.A.  &  Spears  W. (1991) "Learning concept classification
  425.      rules using genetic algorithms". Proc. 12th IJCAI,  651-656,  Sydney,
  426.      Australia: Morgan Kaufmann.
  427.  
  428.      Janikow   C.  (1991)  "Inductive  learning  of  decision  rules  from
  429.      attribute-based examples:  A  knowledge-intensive  GENETIC  ALGORITHM
  430.      approach". TR91-030, The University of North Carolina at Chapel Hill,
  431.      Dept. of Computer Science, Chapel Hill, NC.
  432.  
  433. ------------------------------
  434.  
  435. Subject: Q4.1: What about Alife systems, like Tierra and VENUS?
  436.  
  437.      None of these are Evolutionary Algorithms, but all of  them  use  the
  438.      evolutionary metaphor as their "playing field".
  439.  
  440.  Tierra
  441.      Synthetic organisms have been created based on a computer metaphor of
  442.      organic life in which CPU time is the ``energy'' resource and  memory
  443.      is the ``material'' resource.  Memory is organized into informational
  444.      patterns  that  exploit  CPU  time  for  self-replication.   MUTATION
  445.      generates  new  forms, and EVOLUTION proceeds by natural SELECTION as
  446.      different GENOTYPEs compete for CPU time and memory space.
  447.  
  448.      Observation of nature shows that EVOLUTION by  natural  SELECTION  is
  449.      capable  of  both  OPTIMIZATION and creativity.  Artificial models of
  450.      evolution have demonstrated the optimizing ability of  evolution,  as
  451.      exemplified by the field of GENETIC ALGORITHMs.  The creative aspects
  452.      of evolution have been more elusive to model.  The difficulty derives
  453.      in  part  from  a  tendency  of  models to specify the meaning of the
  454.      ``genome'' of the evolving entities,  precluding  new  meanings  from
  455.      emerging.   I will present a natural model of evolution demonstrating
  456.      both optimization and creativity, in which  the  GENOME  consists  of
  457.      sequences of executable machine code.
  458.  
  459.      From  a single rudimentary ancestral ``creature'', very quickly there
  460.      evolve parasites, which  are  not  able  to  replicate  in  isolation
  461.      because  they  lack  a  large  portion of the GENOME.  However, these
  462.      parasites search for the missing information, and if they  locate  it
  463.      in a nearby creature, parasitize the information from the neighboring
  464.      genome, thereby effecting their own replication.
  465.  
  466.      In some runs, hosts evolve immunity to  attack  by  parasites.   When
  467.      immune  hosts  appear,  they often increase in frequency, devastating
  468.      the parasite POPULATIONs.  In some runs where the community comes  to
  469.      be  dominated by immune hosts, parasites evolve that are resistant to
  470.      immunity.
  471.  
  472.      Hosts sometimes evolve a  response  to  parasites  that  goes  beyond
  473.      immunity,  to  actual  (facultative)  hyper-parasitism.   The  hyper-
  474.      parasite deceives the parasite causing the  parasite  to  devote  its
  475.      energetic  resources  to  replication  of  the hyper-parastie GENOME.
  476.      This drives the parasites to extinction.  Evolving in the absence  of
  477.      parasites,   hyper-parasites   completely   dominate  the  community,
  478.      resulting in a relatively uniform community characterized by  a  high
  479.      degree    of   relationship   between   INDIVIDUALs.    Under   these
  480.      circumstances, sociality evolves, in the form of creatures which  can
  481.      only replicate in aggregations.
  482.  
  483.      The  cooperative  behavior  of  the social hyper-parasites makes them
  484.      vulnerable to a new class of parasites.  These cheaters, hyper-hyper-
  485.      parasites,  insert themselves between cooperating social INDIVIDUALs,
  486.      deceiving the social creatures, causing them to replicate the GENOMEs
  487.      of the cheaters.
  488.  
  489.      The  only genetic change imposed on the simulator is random bit flips
  490.      in the machine code of the creatures.  However,  it  turns  out  that
  491.      parasites  are  very  sloppy  replicators.   They  cause  significant
  492.      RECOMBINATION and rearrangement of  the  GENOMEs.   This  spontaneous
  493.      sexuality  is a powerful force for evolutionary change in the system.
  494.  
  495.      One of the most interesting aspects of this instance of life is  that
  496.      the  bulk  of  the  EVOLUTION  is  based  on adaptation to the biotic
  497.      ENVIRONMENT rather than the physical environment.  It is co-evolution
  498.      that drives the system.
  499.  
  500.      --- "Tierra announcement" by Tom Ray (1991)
  501.  
  502.   How to get Tierra?
  503.      The  complete  source code and documentation (but not executables) is
  504.      available by anonymous FTP at: tierra.slhs.udel.edu:/ (128.175.41.34)
  505.      and life.slhs.udel.edu:/ (128.175.41.33) in the directories: almond/,
  506.      beagle/, doc/, and tierra/.
  507.  
  508.      If you do not have FTP access you may obtain everything on DOS disks.
  509.      For  details, write to: Virtual Life, 25631 Jorgensen Rd., Newman, CA
  510.      95360.
  511.  
  512.      References
  513.  
  514.      Ray, T. S. (1991)  "Is it alive, or is it GA?" in [ICGA91], 527--534.
  515.  
  516.      Ray,  T.  S.  (1991)   "An  approach  to  the  synthesis of life." in
  517.      [ALIFEII], 371--408.
  518.  
  519.      Ray, T. S.  (1991)  "Population dynamics of  digital  organisms."  in
  520.      [ALIFEII-V].
  521.  
  522.      Ray,   T.   S.    (1991)   "Evolution  and  OPTIMIZATION  of  digital
  523.      organisms."  Scientific Excellence in Supercomputing:  The  IBM  1990
  524.      Contest Prize Papers, Eds. Keith R. Billingsley, Ed Derohanes, Hilton
  525.      Brown, III.  Athens, GA, 30602, The Baldwin Press, The University  of
  526.      Georgia.
  527.  
  528.      Ray,  T.  S.  (1992)  "Evolution, ecology and OPTIMIZATION of digital
  529.      organisms."  Santa Fe Institute working paper 92-08-042.
  530.  
  531.      Ray, T. S.  "Evolution, complexity, entropy, and artificial reality."
  532.      submitted Physica D. Avail. as tierra.slhs.udel.edu:/doc/PhysicaD.tex
  533.  
  534.      Ray, T. S.  (1993) "An evolutionary approach  to  synthetic  biology,
  535.      Zen  and the art of creating life.  ARTIFICIAL LIFE 1(1): (in press).
  536.      Avail. as tierra.slhs.udel.edu:/doc/Zen.tex
  537.  
  538.  VENUS
  539.      Steen Rasmussen's (et al.) VENUS I+II "coreworlds"  as  described  in
  540.      [ALIFEII]  and  [LEVY92],  are  inspired by A.K. Dewdney's well-known
  541.      article (Dewdney 1984). Dewdney proposed a game called  "Core  Wars",
  542.      in  which hackers create computer programs that battle for control of
  543.      a computer's "core" memory (Strack 93).  Since computer programs  are
  544.      just  patterns  of  information, a successful program in core wars is
  545.      one that replicates its pattern within the memory, so that eventually
  546.      most  of  the  memory  contains  its  pattern rather than that of the
  547.      competing program.
  548.  
  549.      VENUS is a modification of Core Wars in which the  Computer  programs
  550.      can  mutate, thus the pseudo assembler code creatures of VENUS evolve
  551.      steadily.  Furthermore  each  memory   location   is   endowed   with
  552.      "resources"  which,  like  sunshine  are  added at a steady state.  A
  553.      program must have sufficient resources in the regions  of  memory  it
  554.      occupies  in  order  to  execute.   The input of resources determines
  555.      whether the VENUS ecosystem is a "jungle" or a "desert."   In  jungle
  556.      ENVIRONMENTs,  Rasmussen  et al. observe the spontaneous emergence of
  557.      primitive "copy/split" organisms starting  from  (structured)  random
  558.      initial conditions.
  559.  
  560.      --- [ALIFEII], p.821
  561.  
  562.      Dewdney,  A.K.  (1984) "Computer Recreations: In the Game called Core
  563.      War Hostile Programs Engage in a Battle of Bits", Sci. Amer.  250(5),
  564.      14-22.
  565.  
  566.      Farmer  &  Belin  (1992)  "Artificial  Life:  The  Coming Evolution",
  567.      [ALIFEII], 815-840.
  568.  
  569.      Rasmussen, et al. (1990) "The Coreworld: Emergence and  EVOLUTION  of
  570.      Cooperative  Structures  in  a Computational Chemistry", [FORREST90],
  571.      111-134.
  572.  
  573.      Rasmussen,  et  al.  (1992)  "Dynamics   of   Programmable   Matter",
  574.      [ALIFEII], 211-254.
  575.  
  576.      Strack (1993) "Core War Frequently Asked Questions (rec.games.corewar
  577.      FAQ)"        Avail.        by         anon.          FTP         from
  578.      rtfm.mit.edu:/pub/usenet/news.answers/games/corewar-faq.Z
  579.  
  580.  PolyWorld
  581.      Larry  Yaeger's  PolyWorld as described in [ALIFEIII] and [LEVY92] is
  582.      available via anonymous FTP from ftp.apple.com:/pub/polyworld/
  583.  
  584.      "The subdirectories in this "polyworld" area contain the source  code
  585.      for the PolyWorld ecological simulator, designed and written by Larry
  586.      Yaeger, and Copyright 1990, 1991, 1992 by Apple Computer.
  587.  
  588.      PostScript versions of my ARTIFICIAL LIFE III  technical  paper  have
  589.      now  been added to the directory.  These should be directly printable
  590.      from most machines.  Because some unix systems' "lpr" commands cannot
  591.      handle  very large files (ours at least), I have split the paper into
  592.      Yaeger.ALife3.1.ps and Yaeger.ALife3.2.ps.  These files can be ftp-ed
  593.      in  "ascii"  mode.   For  unix  users I have also included compressed
  594.      versions of both these files (indicated by the .Z suffix),  but  have
  595.      left the uncompressed versions around for people connecting from non-
  596.      unix systems.  I  have  not  generated  PostScript  versions  of  the
  597.      images,  because  they are color and the resulting files are much too
  598.      large to store, retrieve,  or  print.   Accordingly,  though  I  have
  599.      removed  a  Word-formatted  version  of the textual body of the paper
  600.      that used to be here, I have left a  Word-formatted  version  of  the
  601.      color  images.   If  you wish to acquire it, you will need to use the
  602.      binary transfer mode to move it to first your unix host and then to a
  603.      Macintosh  (unless  Word on a PC can read it - I don't know), and you
  604.      may need to do something nasty like use ResEdit to set the file  type
  605.      and  creator to match those of a standard Word document (Type = WDBN,
  606.      Creator = MSWD).  [..]"
  607.  
  608.      --- from the README by Larry Yaeger <larryy@apple.com>
  609.  
  610.  General Alife repositories?
  611.      Also, all of the following FTP sites carry ALIFE related info:
  612.  
  613.      ftp.cognet.ucla.edu:/pub/alife/
  614.      life.anu.edu.au:/pub/complex_systems/alife/
  615.      ftp.cogs.susx.ac.uk:/pub/reports/csrp/
  616.      xyz.lanl.gov:/nlin-sys/
  617.  
  618. ------------------------------
  619.  
  620. Subject: Q5: What about all this Optimization stuff?
  621.  
  622.      Just think of an OPTIMIZATION problem as a black box.  A large  black
  623.      box.  As  large as, for example, a Coca-Cola vending machine. Now, we
  624.      don't know nothing about the inner workings of  this  box,  but  see,
  625.      that  there  are some regulators to play with, and of course we know,
  626.      that we want to have a bottle of the real thing...
  627.  
  628.      Putting this everyday problem into a mathematical model,  we  proceed
  629.      as follows:
  630.  
  631.      (1) we  label all the regulators with x and a number starting from 1;
  632.      the result is a vector x, i.e.  (x_1,...,x_n),  where  n  is  the
  633.      number of visible regulators.
  634.  
  635.      (2) we must find an objective function, in this case it's obvious, we
  636.      want to get k bottles of the real thing, where k is equal  to  1.
  637.      [some  might  want  a  "greater or equal" here, but we restricted
  638.      ourselves to the visible regulators (we all know that sometimes a
  639.      "kick  in  the  right  place" gets use more than 1, but I have no
  640.      idea how to put this mathematically...)]
  641.  
  642.      (3) thus, in the language some mathematicians  prefer  to  speak  in:
  643.      f(x)  =  k  =  1. So, what we have here is a maximization problem
  644.      presented in a form we know from some  boring  calculus  lessons,
  645.      and   we   also   know  that  there  at  least  a  dozen  utterly
  646.      uninteresting techniques to solve problems presented this  way...
  647.  
  648.  What can we do in order to solve this problem?
  649.      We  can  either try to gain more knowledge or exploit what we already
  650.      know about the interior of the black box. If the  objective  function
  651.      turns  out  to  be smooth and differentiable, analytical methods will
  652.      produce the exact solution.
  653.  
  654.      If this turns out to be impossible, we  might  resort  to  the  brute
  655.      force  method  of  enumerating the entire SEARCH SPACE.  But with the
  656.      number of possibilities growing exponentially in  n,  the  number  of
  657.      dimensions  (inputs),  this  method  becomes infeasible even for low-
  658.      dimensional spaces.
  659.  
  660.      Consequently, mathematicians  have  developed  theories  for  certain
  661.      kinds  of  problems  leading  to specialized OPTIMIZATION procedures.
  662.      These  algorithms  perform  well  if  the  black  box  fulfils  their
  663.      respective  prerequisites.   For example, Dantzig's simplex algorithm
  664.      (Dantzig 66) probably  represents  the  best  known  multidimensional
  665.      method capable of efficiently finding the global optimum of a linear,
  666.      hence convex, objective function in a SEARCH SPACE limited by  linear
  667.      constraints.   (A  USENET  FAQ on linear programming is maintained by
  668.      John W. Gregory of Cray Research, Inc.  Try  to  get  your  hands  on
  669.      "linear-programming-faq"  (and  "nonlinear-programming-faq")  that is
  670.      posted monthly to sci.op-research and is mostly interesting to read.)
  671.  
  672.      Gradient  strategies  are  no longer tied to these linear worlds, but
  673.      they smooth their world by exploiting the objective function's  first
  674.      partial  derivatives  one  has to supply in advance. Therefore, these
  675.      algorithms rely on a locally linear internal model of the black  box.
  676.  
  677.      Newton   strategies   additionally   require   the   second   partial
  678.      derivatives, thus building a quadratic internal model.  Quasi-Newton,
  679.      conjugate  gradient  and  variable metric strategies approximate this
  680.      information during the search.
  681.      The deterministic  strategies  mentioned  so  far  cannot  cope  with
  682.      deteriorations,  so  the search will stop if anticipated improvements
  683.      no longer occur. In a multimodal ENVIRONMENT  these  algorithms  move
  684.      "uphill"  from their respective starting points. Hence, they can only
  685.      converge to the next local optimum.
  686.  
  687.      Newton-Raphson-methods might even diverge if  a  discrepancy  between
  688.      their  internal assumptions and reality occurs.  But of course, these
  689.      methods turn out to  be  superior  if  a  given  task  matches  their
  690.      requirements.  Not relying on derivatives, polyeder strategy, pattern
  691.      search and rotating coordinate search should also be  mentioned  here
  692.      because  they  represent  robust  non-linear  OPTIMIZATION algorithms
  693.      (Schwefel 81).
  694.  
  695.      Dealing with technical OPTIMIZATION problems, one will rarely be able
  696.      to write down the objective function in a closed form.  We often need
  697.      a SIMULATION model in order to grasp reality.  In general, one cannot
  698.      even   expect   these   models   to  behave  smoothly.  Consequently,
  699.      derivatives do not exist. That is why  optimization  algorithms  that
  700.      can  successfully  deal  with  black  box-type  situations  habe been
  701.      developed. The increasing applicability is of course paid  for  by  a
  702.      loss  of  "convergence  velocity,"  compared  to algorithms specially
  703.      designed for the given problem.  Furthermore, the guarantee  to  find
  704.      the global optimum no longer exists!
  705.  
  706.  But why turn to nature when looking for more powerful algorithms?
  707.      In  the  attempt  to  create  tools for various purposes, mankind has
  708.      copied, more often instinctively than geniously,  solutions  invented
  709.      by  nature.  Nowadays, one can prove in some cases that certain forms
  710.      or structures are not only well adapted to their ENVIRONMENT but have
  711.      even reached the optimum (Rosen 67). This is due to the fact that the
  712.      laws of nature have remained  stable  during  the  last  3.5  billion
  713.      years.  For  instance,  at branching points the measured ratio of the
  714.      diameters in a system of blood-vessels comes close to the theoretical
  715.      optimum  provided  by  the laws of fluid dynamics (2^-1/3).  This, of
  716.      course, only represents a  limited,  engineering  point  of  view  on
  717.      nature. In general, nature performs adaptation, not optimization.
  718.  
  719.      The idea to imitate basic principles of natural processes for optimum
  720.      seeking procedures emerged more than three decades ago  (cf  Q10,  3.
  721.      Classics).  Although  these  algorithms  have proven to be robust and
  722.      direct OPTIMIZATION tools, it is only in the  last  five  years  that
  723.      they  have caught the researchers' attention. This is due to the fact
  724.      that many people still look at organic EVOLUTION as a giantsized game
  725.      of  dice,  thus ignoring the fact that this model of evolution cannot
  726.      have worked: a human germ-cell comprises approximately 50,000  GENEs,
  727.      each  of  which  consists  of  about  300  triplets of nucleic bases.
  728.      Although the four existing  bases  only  encode  20  different  amino
  729.      acids,  20^15,000,000, ie circa 10^19,500,000 different GENOTYPEs had
  730.      to be tested in only circa 10^17 seconds, the age of our planet.  So,
  731.      simply  rolling  the  dice  could  not have produced the diversity of
  732.      today's complex living systems.
  733.  
  734.      Accordingly,  taking  random  samples   from   the   high-dimensional
  735.      parameter  space  of an objective function in order to hit the global
  736.      optimum must fail (Monte-Carlo search). But  by  looking  at  organic
  737.      EVOLUTION  as  a  cumulative,  highly  parallel  sieving process, the
  738.      results of which pass on slightly modified into the next  sieve,  the
  739.      amazing   diversity   and  efficiency  on  earth  no  longer  appears
  740.      miraculous. When building a model, the point is to isolate  the  main
  741.      mechanisms  which  have  led  to  today's  world  and which have been
  742.      subjected to evolution themselves.  Inevitably, nature  has  come  up
  743.      with  a  mechanism  allowing  INDIVIDUALs  of one SPECIES to exchange
  744.      parts of their genetic information (RECOMBINATION or CROSSOVER), thus
  745.      being able to meet changing environmental conditions in a better way.
  746.  
  747.      Dantzig, G.B.  (1966)  "Lineare  Programmierung  und  Erweiterungen",
  748.      Berlin: Springer. (Linear pogramming and extensions)
  749.  
  750.      Kursawe,  F.  (1994) " Evolution strategies: Simple models of natural
  751.      processes?", Revue Internationale de Systemique, France (to  appear).
  752.  
  753.      Rosen,   R.  (1967)  "Optimality  Principles  in  Biologie",  London:
  754.      Butterworth.
  755.  
  756.      Schwefel, H.-P. (1981) "Numerical OPTIMIZATION of  Computer  Models",
  757.      Chichester: Wiley.
  758.  
  759. ------------------------------
  760.  
  761. End of ai-faq/genetic/part3
  762. ***************************
  763.